package main

import "fmt"

//定义一个双向链表
type ListNode struct {
	Value int
	Prev  *ListNode
	Next  *ListNode
}

//定义一个双向链表
type DoubleList struct {
	//头指针
	Head *ListNode
	//尾指针
	Tail   *ListNode
	Length int
}

//在双向链表尾部追加一个元素
func (list *DoubleList) Append(x int) {
	node := &ListNode{Value: x}
	tail := list.Tail
	if tail == nil {
		list.Head = node
		list.Tail = node
	} else {
		tail.Next = node
		node.Prev = tail
		list.Tail = node
	}
	list.Length += 1
}

//获取第idx个元素
func (double *DoubleList) Get(idx int) *ListNode {
	if double.Length <= idx {
		return nil
	}
	curr := double.Head
	for i := 0; i < idx; i++ {
		curr = curr.Next
	}
	return curr

}

//添加元素
func (double *DoubleList) InsertAfter(prevNode *ListNode, x int) {
	node := &ListNode{Value: x}
	if prevNode.Next == nil {
		double.Append(x)
		prevNode.Next = node
		node.Prev = prevNode
	}
	nextNode := prevNode.Next
	nextNode.Prev = node
	node.Next = nextNode
	prevNode.Next = node
	node.Prev = prevNode
}

//链表的遍历
func (list *DoubleList) Traverse() {
	curr := list.Head
	for curr != nil {
		fmt.Printf("%d", curr.Value)
		curr = curr.Next
	}
	fmt.Println()
}

func main() {
	list := new(DoubleList)
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Append(4)
	list.Append(5)
	list.Traverse()

	node := list.Get(3)
	list.InsertAfter(node, 9)

	list.Traverse()
}
